python heapq 모듈

파이썬에서 기본적으로 제공하는 heapq 모듈은 우선순위 큐 알고리즘을 제공한다.
리스트를 인덱스 0부터 시작하는 최소힙 형태로 정렬한다.

자세한 사항은 python 공식문서에 잘 서술되어 있다.
https://docs.python.org/ko/3/library/heapq.html

import

import heapq

힙 생성하기

heapq 모듈은 리스트를 최소 힙처럼 다룰 수 있게 도와준다.
즉, 리스트를 힙으로 생성하면 된다.

heap = []

힙에 원소 추가

heappush() 함수를 이용해서 힙에 원소를 추가할 수 있다.

첫번째 인자는 힙 리스트
두번째 인자는 추가할 원소

heapq.heappush(heap, 10)
heapq.heappush(heap, 6)
heapq.heappush(heap, 13)
heapq.heappush(heap, 5)
print(heap)
# [5, 6, 13, 10]

힙에서 원소 삭제

heappop() 함수 사용.
가장 작은 원소를 삭제 후에 반환한다.

print(heappop(heap))
# 5

기존 리스트를 힙으로 변환

heapify 함수를 사용

리스트를 인자로 넘긴다.

heap = [4, 1, 7, 3, 8, 5]
heapify(heap)
print(heap)
# [1, 3, 5, 4, 8, 7]

max heap은?

[?] 최대 힙은 어떻게 사용할 수 있을지 고민을 했었다. 직접 구현해야하나 하고 말이다.
https://hellominchan.tistory.com/231 에서 좋은 방법을 소개해주어서 정리하였다.

음수값 활용

인자를 음수화하고 삽입하고 출력할 때 다시 양수화하는 방법

heapq.heappush(heap, -10)
heapq.heappush(heap, -6)
heapq.heappush(heap, -13)
heapq.heappush(heap, -5)

print(heap)
# [-13, -6, -10, -5]

튜플 사용

음수값 활용과 비슷하지만 튜플로 음수화한 값으로 정렬하고 두번째 요소로 원래 값을 넣는 방법

heapq.heappush(hq, (-1, 1))
heapq.heappush(hq, (-2, 2))
heapq.heappush(hq, (-3, 3))
 
print(heapq.heappop(hq)[1])  # print결과 : 3
print(heapq.heappop(hq)[1])  # print결과 : 2
print(heapq.heappop(hq)[1])  # print결과 : 1